# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/28
"""

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5


思路：
因为输入是排序好的，只需要选择中间的值作为根，左右分别构建子树
"""

# Definition for a binary tree node.
from LeetCode.初级算法.树.遍历二叉树 import pre_order_traversal_recursion


class TreeNode(object):
    def __init__(self, val, l, r):
        self.val = val
        self.left = l
        self.right = r


class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 1:
            return TreeNode(nums[0], None, None)
        if nums is None:
            return None
        if len(nums) == 0:
            return None

        i = len(nums)
        pre = nums[0:int(i / 2)]
        last = nums[int(i / 2) + 1:]
        left = self.sortedArrayToBST(pre)
        right = self.sortedArrayToBST(last)
        node = TreeNode(nums[int(i / 2)], left, right)
        return node


if __name__ == "__main__":
    solution = Solution()
    bst = solution.sortedArrayToBST([1, 2, 3, 4])
    pre_order_traversal_recursion(bst)
